#ifndef coin_H
#define coin_H

#include<iostream>
#include<algorithm>
#include<vector>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define INF 1000000000
using namespace std;
/**
 * @brief 用动态规划算法解决硬币找零问题。
 * @param s[4] 四种硬币的数量
 * @param n 需要得到的总金额
 * @return 如果有解，则返回最少用到的硬币数，否则返回INF
 */
int dp(int s[4],int n){
	int c[4]={1,5,10,25};
	vector<int> f(n+100,INF);//f[n]表示构成n美分所需的最小硬币数
	f[0]=0;
	for(int i=0;i<4;++i){
		for(int j=n;j;--j){
			for(int k=1;k<=s[i];++k){
				if(j<k*c[i]) break;
				f[j]=min(f[j],f[j-k*c[i]]+k);
			}
		}
	}
	return f[n];
}
/**
 * @brief 用贪心算法解决硬币找零问题。
 * @param s[4] 四种硬币的数量
 * @param n 需要得到的总金额
 * @return 如果有解，则返回最少用到的硬币数，否则返回INF
 */
int greedy(int s[4],int n){
	int ans=INF;
	for(int k=0;k<=s[3]&&25*k<=n;++k){//枚举拿走的25美分硬币数量k
		int x=n-25*k;
		int n2=min(s[2],x/10);//拿走的10美分硬币数量，尽量多拿
		x=x-10*n2;
		int n1=min(s[1],x/5);//拿走的5美分硬币数量，尽量多拿
		x=x-5*n1;
		if(x<=s[0]) ans=min(ans,k+n2+n1+x);//最后剩下x美分用1美分凑齐
	}
	return ans;
}

#endif